package sort.seniorSort;


import java.util.Arrays;

import static sort.SortCompare.getArray;
/*
    索引从0开始的堆排序
 */
public class Heap {
    public static void sort(Comparable[] a) {
        System.out.println(isHeapSorted(a));
        int N = a.length - 1;
        for (int i = (N - 1) / 2; i >= 0; i--) {
            sink(a, i, N);
        }
        System.out.println(isHeapSorted(a));
        while (N >= 1) {
            exch(a, 0, N--);
            sink(a, 0, N);
        }
    }

    private static void sink(Comparable[] a, int k, int N) {
        while (2 * k + 1 <= N) {
            int j = 2 * k + 1;
            if (j < N && less(a, j, j + 1)) j++;
            if (!less(a, k, j)) break;
            exch(a, k, j);
            k = j;
        }
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static boolean less(Comparable[] a, int i, int j) {
        return a[i].compareTo(a[j]) < 0;
    }

    private static boolean isHeapSorted(Comparable[] a){
        int N = a.length - 1;
        for (int i = 0; i<(N-1)/2; i++){
            if (less(a, i, 2*i+1) || less(a, i, 2*i+2)) return false;
        }
        return true;
    }
    private static boolean isSorted(Comparable[] a){
        int N = a.length;
        for (int i = 1; i<N;i++){
            if (less(a, i, i-1)) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Comparable[] array = getArray(10);
        System.out.println("排序之前：" + Arrays.asList(array));
        sort(array);
        System.out.println("排序之后：" + Arrays.asList(array));
        System.out.println(isSorted(array));
    }
}
